package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/trim-a-binary-search-tree/">修剪二叉搜索树(Trim a Binary Search Tree)</a>
 * <p>给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树<b>不应该</b>改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。</p>
 * <p>所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,0,2], low = 1, high = 2
 *                  1               1
 *                 / \      ==>      \
 *                0   2               2
 *      输出：[1,null,2]
 *
 * 示例 2：
 *      输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
 *                  3               3
 *                 / \             /
 *                0   4           2
 *                 \        ==>  /
 *                  2           1
 *                 /
 *                1
 *      输出：[3,2,null,1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数在范围 [1, 10^4] 内</li>
 *     <li>0 <= Node.val <= 10^4</li>
 *     <li>树中每个节点的值都是 唯一 的</li>
 *     <li>题目数据保证输入是一棵有效的二叉搜索树</li>
 *     <li>0 <= low <= high <= 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/11 16:58
 */
public class LC0669TrimBinarySearchTree_M {

    static class Solution {
        public TreeNode trimBST(TreeNode root, int low, int high) {
            return trimBSTByIteration(root, low, high);
            //return trimBSTByRecursion(root, low, high);
        }

        private TreeNode trimBSTByIteration(TreeNode root, int low, int high) {
            if (root == null) {
                return null;
            }
            while (root != null && (root.val < low || root.val > high)) {
                if (root.val < low) {
                    root = root.right;  // 需要加大节点值
                }
                if (root.val > high) {
                    root = root.left;   // 需要减小节点值
                }
            }
            if (root == null) {
                return null;
            }
            // 减左枝
            // node 的左结点为空结点：不需要修剪
            // node 的左结点非空：对于node.left.val < low，那么left以及left的左子树都不符合要求，使node.left = node.left.right，然后再继续对node的左子树进行修剪
            // node 的左结点非空：对于node.left.val > high，因为node.val < high，所以node.left.val一定也小于high；此情况不会出现
            TreeNode currNode = root;
            while (currNode.left != null) {
                if (currNode.left.val < low) {
                    currNode.left = currNode.left.right;
                } else {
                    currNode = currNode.left;
                }
            }
            // 减右枝
            // node 的右结点为空结点：不需要修剪
            // node 的右结点非空：对于node.right.val > high，那么right以及right的右子树都不符合要求，使node.right = node.right.left，然后再继续对node的右子树进行修剪
            // node 的右结点非空：对于node.right.val < low，因为node.val > low，所以node.right.val一定也大于low；此情况不会出现
            currNode = root;
            while (currNode.right != null) {
                if (currNode.right.val > high) {
                    currNode.right = currNode.right.left;
                } else {
                    currNode = currNode.right;
                }
            }
            return root;
        }

        private TreeNode trimBSTByRecursion(TreeNode currNode, int low, int high) {
            if (currNode == null) {
                return null;
            }
            if (currNode.val < low) {
                return trimBSTByRecursion(currNode.left, low, high);
            }
            if (currNode.val > low) {
                return trimBSTByRecursion(currNode.right, low, high);
            }
            currNode.left = trimBSTByRecursion(currNode.left, low, high);
            currNode.right = trimBSTByRecursion(currNode.right, low, high);
            return currNode;
        }
    }
}
